package com.example.mykotlinapp.test

/**
 * 给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。

 

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

进阶:

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例:

输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7
 *
 * @author zhudeshuai
 * @since 2019/8/8
 */


fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
    var target1 = revertListNode(l1)
    var target2 = revertListNode(l2)
    return if (target1 == null || target2 == null) {
        target1 ?: target2
    }else {
        var result:ListNode? = null
        var needPlusOne = false
        while (target1 != null && target2 != null){
            var tmpValue = target1.`val` + target2.`val`
            if(needPlusOne){
                tmpValue++
            }
            if(tmpValue > 9){
                tmpValue -= 10
                needPlusOne = true
            }else {
                needPlusOne = false
            }
            val tmp = ListNode(tmpValue)
            tmp.next = result
            result = tmp
            target1 = target1.next
            target2 = target2.next
        }
        //其中至少有一个为空
        while (target1 != null){
            val tmp = ListNode(
                if(needPlusOne) {
                    var tmpValue = target1.`val` + 1
                    if(tmpValue > 9) {
                        tmpValue -= 10
                    }else {
                        needPlusOne = false
                    }
                    tmpValue
                }else {
                    target1.`val`
                }
            )
            tmp.next = result
            result = tmp
            target1 = target1.next
        }
        while (target2 != null){
            val tmp = ListNode(
                if(needPlusOne) {
                    var tmpValue = target2.`val` + 1
                    if(tmpValue > 9) {
                        tmpValue -= 10
                    }else {
                        needPlusOne = false
                    }
                    tmpValue
                }else {
                    target2.`val`
                }
            )
            tmp.next = result
            result = tmp
            target2 = target2.next
        }
        //可能最高位是10需要进位
        if(needPlusOne){
            val tmp = ListNode(1)
            tmp.next = result
            return tmp
        }
        result
    }
}


fun revertListNode(listNode: ListNode?): ListNode? {
    var result: ListNode? = null
    var target = listNode
    while (target != null) {
        val tmp = ListNode(target.`val`)
        tmp.next = result
        result = tmp
        target = target.next
    }
    return result
}

fun main() {
    val l1 = ListNode(7, ListNode(4, ListNode(4, ListNode(3))))
    val l2 = ListNode(5, ListNode(6, ListNode(4)))
    val addTwoNumbers = addTwoNumbers(l1, l2)
    println(addTwoNumbers)
}